package treeNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    /**
     * 相同的树
     * @param p 二叉树
     * @param q 二叉树
     * @return 如果相同返回 true,否则 false
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(((p==null&&q!=null)||(p!=null&&q==null) )){
            return false;
        }else if(  p.val!=q.val){
            return false;
        }else if((this.isSameTree(p.left,q.left))&&(this.isSameTree(p.right,q.right))){
            return true;
        }else{
            return false;
        }
    }

    /**
     * 给定一个二叉树，检查它是否是镜像对称的
     * 思路，left 的right 与 right 的left  相等
     *      left的left 与 right的right相等
     * @param root
     * @return
     */
    public boolean isSymmetric(TreeNode root) {
        if(root==null){
            return true;
        }else {
            return isSymmetric(root.left,root.right);
        }
    }

    public boolean isSymmetric(TreeNode left,TreeNode right){
        if(left==null&&right==null){
            return true;
        }else if(left!=null&&right!=null){
            if(left.val==right.val){
                return isSymmetric(left.left,right.right)&&isSymmetric(left.right,right.left);
            }else{
                return false;
            }
        }else{
            return false;
        }
    }

    /**
     * 2层序遍历
     * 思路，迭代器遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> nodes = new ArrayList<TreeNode>();
        if(root==null){
            return result;
        }
        nodes.add(root);
        result.add(getOrder(nodes));
        while(hasNext(nodes)){
            nodes = next(nodes);
            result.add(getOrder(nodes));
        }
        return result;
    }

    /**
     * 4锯齿层序遍历
     * 思路，迭代器遍历
     * @param root
     * @return
     */
    public List<List<Integer>> levelZOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        List<TreeNode> nodes = new ArrayList<TreeNode>();
        int sort =0;
        if(root==null){
            return result;
        }
        nodes.add(root);
        result.add(getOrder(nodes,sort));
        sort++;
        while(hasNext(nodes)){
            nodes = next(nodes);
            result.add(getOrder(nodes,sort));
            sort++;
        }
        return result;
    }



    public boolean hasNext(List<TreeNode> nodes){
        if(nodes==null){
            return false;
        }
        for(TreeNode node:nodes){
            if(node!=null&&(node.left!=null||node.right!=null)){
                return true;
            }
        }
        return false;
    }

    /**
     * 获取当层的值
     * @param nodes
     * @return
     */
    public List<Integer> getOrder(List<TreeNode> nodes){
        List<Integer> item = new ArrayList<Integer>();
        for(TreeNode node:nodes){
            if(node!=null){
                item.add(node.val);
            }
        }
        return item;
    }

    /**
     * 获取当层的值
     * @param nodes
     * @param sort 偶数正序，奇数倒序
     * @return
     */
    public List<Integer> getOrder(List<TreeNode> nodes,int sort){
        List<Integer> item = new ArrayList<Integer>();
        for(TreeNode node:nodes){
            if(node!=null){
                item.add(node.val);
            }
        }
        if(sort%2!=0){
            Collections.reverse(item);
        }

        return item;
    }


    /**
     * 获取下一层的 nodes
     * @param nodes
     * @return
     */
    public List<TreeNode> next(List<TreeNode> nodes){
        List<TreeNode> nextNodes = new ArrayList<TreeNode>();
        for(TreeNode node:nodes){
            if(node!=null){
                nextNodes.add(node.left);
                nextNodes.add(node.right);
            }

        }
        return nextNodes;
    }

    /**
     * 给定一个二叉树，找出其最大深度
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        int depth =0;

        if(root==null){
            return 0;
        }
        List<TreeNode> nodes = new ArrayList<TreeNode>();
        nodes.add(root);
        depth++;

        while(hasNext(nodes)){
            nodes = next(nodes);
            depth++;
        }
        return depth;
    }


    public static void main(String[] args) {
        Solution solution =  new Solution();
//        TreeNode p = new TreeNode(1,new TreeNode(2),new TreeNode(3));
//       TreeNode q = new TreeNode(1,new TreeNode(2),new TreeNode(3));
//        System.out.println(new Solution().isSameTree(p,q));

//        TreeNode root = new TreeNode(1,
//                new TreeNode(2,new TreeNode(3,new TreeNode(5),new TreeNode(2)),new TreeNode(4,new TreeNode(3),new TreeNode(4))),
//                new TreeNode(2,new TreeNode(4,new TreeNode(4),new TreeNode(3)),new TreeNode(3,new TreeNode(2),new TreeNode(5)))
//        );
//        System.out.println(solution.isSymmetric(root));

         TreeNode root = new TreeNode(1,
                new TreeNode(2,new TreeNode(3,new TreeNode(5),new TreeNode(2)),new TreeNode(4,new TreeNode(3),new TreeNode(4))),
                new TreeNode(3,new TreeNode(5,new TreeNode(4),new TreeNode(3)),new TreeNode(6,new TreeNode(2),new TreeNode(7)))
        );
//        List<List<Integer>> orders = solution.levelOrder(root);
//        List<List<Integer>> orders = solution.levelOrder(null );
//        for(List<Integer> order:orders){
//            System.out.println(order);
//        }

//        List<List<Integer>> orders = solution.levelZOrder(root );
//        for(List<Integer> order:orders){
//            System.out.println(order);
//        }

        System.out.println(solution.maxDepth(root));
    }

}
